//给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。 
//
// 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 
//
// 
//
// 示例 1： 
//
// 
//输入: s = "leetcode", wordDict = ["leet", "code"]
//输出: true
//解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。
// 
//
// 示例 2： 
//
// 
//输入: s = "applepenapple", wordDict = ["apple", "pen"]
//输出: true
//解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
//     注意，你可以重复使用字典中的单词。
// 
//
// 示例 3： 
//
// 
//输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
//输出: false
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 300 
// 1 <= wordDict.length <= 1000 
// 1 <= wordDict[i].length <= 20 
// s 和 wordDict[i] 仅由小写英文字母组成 
// wordDict 中的所有字符串 互不相同 
// 
//
// Related Topics 字典树 记忆化搜索 数组 哈希表 字符串 动态规划 👍 2396 👎 0


package com.tyrone.leetcode.editor.cn;

import java.util.Arrays;
import java.util.List;

public class WordBreak {
    public static void main(String[] args) {
        Solution solution = new WordBreak().new Solution();
        System.out.println(solution.wordBreak("leetcode", Arrays.asList("leet", "code")));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {


        /**
         * 第一想法  感觉可以先暴力搜索试试
         * 35 / 46 个通过的测试用例 说明这么写解法没有问题 就是复杂度太高了
         * 写完后面动态规划之后，看到别人的是这样写的
         *
         * @param s
         * @param wordDict
         * @return
         */
//        public boolean wordBreak(String s, List<String> wordDict) {
//            for (String word : wordDict) {
//                if (s.length()==0||(s.startsWith(word) && wordBreak(s.substring(word.length()), wordDict)))
//                    return true;
//            }
//            return false;
//        }


        List<String> wd;
        String s1;

        public boolean wordBreak(String s, List<String> wordDict) {
            wd = wordDict;
            s1 = s;
            boolean[] processed = new boolean[s.length()];
            return process(0, processed);
        }

        public boolean process(int offset, boolean[] processed) {
            if (offset >= s1.length()) {
                return true;
            }
            if (processed[offset]) {
                return false;
            }
            for (String word : wd) {
                if (s1.startsWith(word, offset)) {
                    if (process(offset + word.length(), processed)) {
                        return true;
                    }
                }
            }
            processed[offset] = true;
            return false;
        }


        /**
         * 动态规划 dp[i]表示 i以前的字符串可以由wordDict里面的字符串组成
         * 所以对于dp[i] 来说  需要不断去判断0~i-1是不是可以由wordDict里面的字符串组成 也就是dp[j] == true?
         * 如果可以的话 还要在判断j到i之间的字符串是否是在wordDict中 如果是的话 才能真正说明 dp[i] == true
         * @param s
         * @param wordDict
         * @return
         */
//        public boolean wordBreak(String s, List<String> wordDict) {
//            boolean[] dp = new boolean[s.length()+1];
//            dp[0] = true;
//            for (int i = 1; i <= s.length(); i++) {
//                for (int j = 0; j < i; j++) {
//                    // 在i之前找到 一个0～j 是由wordDict组成的 并且 j～i也是之间的单词也是属于的 那么dp[i]肯定是true
////                    if (dp[j] && wordDict.contains(s.substring(j,i))){
////                        dp[i] = true;
////                        break;
////                    }
//                    //这种可能更直观 遍历wordDict往回推
//                    for(String word:wordDict){
//                        int d = word.length();
//                        if(d <= i && dp[i-d] && s.substring(i-d,i).equals(word)){
//                            dp[i]=true;
//                            break;
//                        }
//                    }
//                }
//            }
//            return dp[s.length()];
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}